//
//  Sort.m
//  Study
//
//  Created by 振兴 刘 on 2017/9/23.
//  Copyright © 2017年 振兴 刘. All rights reserved.
//

#import "Sort.h"

@implementation Sort

+ (void)swap:(NSMutableArray*)array first:(NSInteger)first second:(NSInteger)second {

    if (first == second)
        return;
    
    id temp = nil;
    temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

+ (void)bubblingSort:(NSMutableArray*)array {
    
    //@(8),@(2), @(5), @(4), @(9), @(2), @(6), @(7), @(3), @(0), @(1),@(-1)
    
    for (int i = 0; i < array.count-1; i++) {
        for (int j = 0; j < array.count-1-i; j++) {
            
            if (array[j] > array[j+1])
                [self swap:array first:j second:j+1];
        }
    }
}

+ (void)selectSort:(NSMutableArray*)array {
    
    for (int i = 0; i < array.count-1; i++) {
        
        int min = i;
        for (int j = min+1; j <array.count; j++) {
            
            if (array[j] < array[min])
                min = j;
        }
        
        if (min != i)
            [self swap:array first:i second:min];
    }
}

+ (void)insetSort:(NSMutableArray*)array {
    
    for (int i = 1; i < array.count; i++) {
        
        int cur = [array[i] intValue];
        int j = i - 1;
        while (j >= 0 && [array[j] intValue] > cur) {
            
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = @(cur);
    }
}

//交换
+ (void)heapify:(NSMutableArray*)array size:(NSInteger)size index:(NSInteger)index {

    NSInteger max = index;
    NSInteger left = 2*index + 1;
    NSInteger right = 2*index + 2;
    
    if (left < size && [array[left] intValue] > [array[max] intValue])
        max = left;
    
    if (right < size && [array[right] intValue] > [array[max] intValue])
        max = right;
    
    if (max != index) {
     
        [self swap:array first:index second:max];
        [self heapify:array size:size index:max];
    }
}

+ (void)buildHeap:(NSMutableArray*)array size:(NSInteger)size {

    //size：排序元素个数
    //树最后一个分支中，3个结点中的根结点：(size-1)/2
    for (NSInteger i = (size-1)/2; i >= 0; i--) {
        [self heapify:array size:size index:i];
    }
}

+ (void)heapSort:(NSMutableArray*)array {
    
    for (NSInteger i = array.count-1; i>=0 ; i--) {
        
        [self buildHeap:array size:i+1];
        [self swap:array first:0 second:i];
    }
}

+ (void)quickSortExt:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right {
    
    NSInteger i = left;
    NSInteger j = right;
    NSInteger pivot = (i+j)/2;
    
    while (i <= j) {
        
        while ([array[i] intValue] < [array[pivot] intValue]) {
            i++;
        }
        
        while ([array[j] intValue]> [array[pivot] intValue]) {
            j--;
        }
        if (i <= j) {
            [self swap:array first:i second:j];
            i++;
            j--;
        }
    }
    
    if (left < j)
        [self quickSortExt:array left:left right:j];
    
    if (i < right)
        [self quickSortExt:array left:i right:right];
}

+ (void)quickSort:(NSMutableArray*)array {
    
    [self quickSortExt:array left:0 right:array.count-1];
}

@end












